%%%-------------------------------------------------------------------
%%% File    : p25.erl
%%% Author  : Plamen Dragozov <plamen at dragozov.com>
%%% Description : 
%%% The Fibonacci sequence is defined by the recurrence relation:
%%%     F_(n) = F_(n−1) + F_(n−2), where F_(1) = 1 and F_(2) = 1.
%%% Hence the first 12 terms will be:
%%%     F_(1) = 1
%%%     F_(2) = 1
%%%     F_(3) = 2
%%%     F_(4) = 3
%%%     F_(5) = 5
%%%     F_(6) = 8
%%%     F_(7) = 13
%%%     F_(8) = 21
%%%     F_(9) = 34
%%%     F_(10) = 55
%%%     F_(11) = 89
%%%     F_(12) = 144
%%% The 12th term, F_(12), is the first term to contain three digits.
%%% What is the first term in the Fibonacci sequence to contain 1000 digits?
%%% Created : 10 Dec 2008 by  <>
%%%-------------------------------------------------------------------
-module(p25).

%% API
-compile(export_all).

%%====================================================================
%% API
%%====================================================================
%%--------------------------------------------------------------------
%% Function: solution(N) -> int()
%% Description: The first Fibonacci number to contain N digits
%%--------------------------------------------------------------------
solution(N) ->
    fib([1], [1], N, 3).


%%====================================================================
%% Internal functions
%%====================================================================
fib(N1, N2, MaxDigits, Counter) ->
    {Count, Sum} = sum(N1, N2),
    case MaxDigits > Count of
        true ->
            fib(N2, Sum, MaxDigits, Counter+1);
        _ ->
            Counter
    end.

sum(Digits1, Digits2) ->
    sum(lists:reverse(Digits1), lists:reverse(Digits2), 0, 0, []).

sum([], [], 0, Count, Acc)->
    {Count, Acc};
sum([], [], Prev, Count, Acc) ->
    sum([], [], Prev div 10, Count + 1, [Prev rem 10|Acc]);
sum([H1|T1], [], Prev, Count, Acc) ->
    New = H1 + Prev,
    Div = New div 10,
    Rem = New rem 10,
    sum(T1, [], Div, Count + 1, [Rem|Acc]);
sum([], [H2|T2], Prev, Count, Acc) ->
    New = H2 + Prev,
    Div = New div 10,
    Rem = New rem 10,
    sum([], T2, Div, Count + 1, [Rem|Acc]);
sum([H1|T1], [H2|T2], Prev, Count, Acc) ->
    New = H1 + H2 + Prev,
    Div = New div 10,
    Rem = New rem 10,
    sum(T1, T2, Div, Count + 1, [Rem|Acc]).

